package com.squirrel.michale.search8;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/1/31 8:33 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode1760 {

    /**
     *
     *
     * @param nums
     * @param maxOperations
     * @return
     */
    public int minimumSize(int[] nums, int maxOperations) {

        // balls 经历ops次拆分后获得的开销 看成 penalty = balls/(ops+1),很显然该函数是单调递减，当Sum(ops)<=maxOperations时penalty的值就是答案
        // case 1: balls <= penalty ,ops = 0
        // case 2: balls > penalty
        // case 2.1: balls%penalty == 0,  ops = balls/penalty -1
        // case 2.2: balls%penalty != 0,  ops = Math.ceil(balls/penalty) -1
        // ops = (balls+penalty-1)/penalty -1 ==> ops = (balls-1)/penalty
        int left = 1;
        int right = Arrays.stream(nums).max().getAsInt();

        int middle = 0;
        while (left < right) {
            middle = left + ((right - left) >> 1);
            int ops = 0;
            for (int i = 0; i < nums.length; i++) {
                ops += (nums[i] - 1) / middle;
            }
            if (ops <= maxOperations) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        return left;
    }


    public static void main(String[] args) {
        LeetCode1760 leetCode1760 = new LeetCode1760();

        int[] nums = new int[]{7, 17};
        int maxOperations = 2;
        System.out.println(leetCode1760.minimumSize(nums, maxOperations));

    }


}
